package 算法.动态规划;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-14
 */
public class JZ71跳台阶扩展问题 {
    //动态规划
    /**
     * 对于最后一级台阶，我们可以由倒数第二级台阶跳1步，也可以由倒数第三级太极跳两步
     * f(n)=f(n−1)+f(n−1)=2∗f(n−1)
     */
    public int jumpFloorII(int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=target;i++){
            dp[i] = 2 * dp[i-1];
        }
        return  dp[target];
    }

    //递归
    public int jumpFloorII2(int target) {
        if(target<=1)
            return  target;
        return 2 * jumpFloorII2(target-1);
    }

    //数学规律
    //f(n)=f(n−1)+f(n−1)=2∗f(n−1) ===> f(n) = 2^n-1
    public int jumpFloorII3(int target) {
        if(target <= 1)
            return 1;
        //直接次方
        return (int)Math.pow(2, target - 1);
    }
}
